\chapter{Вопрос № 25}

Перечисление орграфов и связных оргафов, перечисление Эйлеровых графов. Доказательство теоремы Кэли о количестве помеченных деревьев с помощью кода Прюфера.

\section{Перечисление орграфов}

Всего ориентированных помеченных графов на $n$ вершинах существует:
\begin{equation}
	c_n = 2^{n\left(n-1\right)}
\end{equation}
теперь, если
\[
	H\left(x\right) = 1 + c_1x + c_2 \frac{x^2}{2!} + c_3 \frac{x^3}{3!} + ...
\]
описывает все ориентированные графы, а функция:
\[
	F\left(x\right) = a_1x + a_2\frac{x^2}{2!} + a_3\frac{x^3}{3!} + ...
\]
описывает связные ориентированные графы, то они связаны соотношением:
\begin{equation}
	H\left(x\right) = exp\left(F\left(x\right)\right)
\end{equation}
откуда получаем продифференцировав:
\[
	\begin{split}
		& H'\left(x\right)=F'\left(x\right)H\left(x\right) \Leftrightarrow \\
		& c_1 + c_2 x + c_2 \frac{x^2}{2!} + ... = \left(a_1 + a_2x + a_3\frac{x^2}{2!} + ...\right)\left(1 + c_1x + c_2\frac{x^2}{2!} + ...\right) \Leftrightarrow \\
		& a_{n+1} = c_{n+1} - \sum_{i=1}^{n} \binom{n}{i} c_{i}a_{n-i+1} = c_{n+1} - \sum_{i=0}^{n-1} \binom{n}{i} c_{n-i}a_{i+1}
	\end{split}
\]

\section{Эйлеровы графы}

Число помеченных графов на $n$ вершинах, в которых все вершины имеют четную степень равно числу помеченных графов на $n-1$ вершине, чтобы это показать достаточно построить любой граф на $n-1$ вершине, количество нечетных вершин в ней четно, если добавить вершину с пометкой $n$ и соединить ее со всеми нечетными вершинами, получим нужный граф, итого имеем:
\begin{equation}
	c_n = 2^{\binom{n-1}{2}}
\end{equation}
тогда пользуясь формулой аналогичной предыдущей задаче получаем количество связных четных помеченных графов - Эйлеровых графов.

\section{Код Прюфера}

Пусть имеется дерево, вершины которого помечены номаерами от 1 до $n$. Соспоставим такому дереву последовательность чисел следующим образом: выбираем лист дерева с минимальным номером, записываем номер смежной с ним вершины в код, а сам лист и инцедентное ребро удаляем из дерева, так продолжаем пока не останется всего одна вершина.

Заметим, что количество чисел в коде будет равно $n-1$, а кроме того, последним числом в коде будет число $n$, поэтому можно ограничиться рассмотрением последовательности из $n-2$ чисел.

Далее заметим, что номер вершины встречается в коде Прюфера в том и только том случае, если вершина не является листом, либо имеет метку $n$. Далее покажем, что по любой последовательности из $n-2$ чисел от 1 до $n$ можно построить дерево. Для $n=2$ все очевидно, сделаем переход от $n$ к $n+1$. Пусть у нас есть последовательность из $n-1$ числа в диапазоне от 1 до $n+1$, найдем минимальное число из $\left\{1,...,n+1\right\}$ не лежащее в последовательности. Вершина с этим номером была удалена первой из дерева при построении кода Прюфера, следовательно она была соеденена с вершиной, метка которой стоит первой в коде Прюфера, теперь выкинем из последовательности первое число, а все номера большие этого числа уменьшаем на единицу и получаем последовательность меньшей длинны, для которой по индукции утверждение доказано.

Таким образом код Прюфера задает биекцию между помеченными деревьями на $n$ вершинах и последовательностями из $n-2$ чисел в диапазоне от 1 до $n$, откуда получаем, что общее число помеченных деревьев на $n$ вершинах равно:
\begin{equation}
	n^{n-2}
\end{equation}
